◀ Prev · Parts · Full · Next ▶

An effective measure 0 set can be interpreted as a Turing machine that is able to tell, given an infinite binary string, whether the string looks random at levels of statistical significance. The set is the intersection of shrinking sets U 1 ⊃ ⊃ U 2 ⊃ ⊃ U 3 ⊃ ⊃ ⋯ ⋯ {\displaystyle U_{1}\supset U_{2}\supset U_{3}\supset \cdots } , and since each set U n {\displaystyle U_{n}} is specified by an enumerable sequence of prefixes, given any infinite binary string, if it is in U n {\displaystyle U_{n}} , then the Turing machine can decide in finite time that the string does fall inside U n {\displaystyle U_{n}} . Therefore, it can "reject the hypothesis that the string is random at significance level 2 − − n {\displaystyle 2^{-n}} ". If the Turing machine can reject the hypothesis at all significance levels, then the string is not random. A random string is one that, for each Turing-computable test of randomness, manages to remain forever un-rejected at some significance level.cite-ref-8[8]

◀ Prev · Parts · Full · Next ▶